﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Atlepage.State;

namespace Atlepage.Syntactic
{
    public class ParserFactory
    {
        Dictionary<string, NonTerminal> nonTerms = new Dictionary<string, NonTerminal>();
        Dictionary<string, Terminal> terms = new Dictionary<string, Terminal>();
        List<Production> productions = new List<Production>();
        List<LRItemSet> states = new List<LRItemSet>();
        Parser parser;

        public ParserFactory()
        {
        }

        public static Parser CreateParser(Type type, IEnum kind, object actor, List<string> errors, List<string> warnings)
        {
            ParserFactory factory = new ParserFactory();
            if (!factory.LoadFromDisk())
            {
                if (factory.Generate(type, kind, errors, warnings))
                    factory.SaveToDisk();
                else
                    return null;
            }
            return factory.CreateParser(actor);
        }

        public bool LoadFromDisk()
        {
            Manager<Parser> manager = new Manager<Parser>(".pll");
            parser = manager.Load();
            return parser != null;
        }

        public void SaveToDisk()
        {
            Manager<Parser> manager = new Manager<Parser>(".pll");
            manager.Save(parser);
        }

        public Parser CreateParser(object actor)
        {
            Parser parser = this.parser.Clone();
            parser.Initialize(actor);
            return parser;
        }

        public bool Generate(Type type, IEnum kind, List<string> errors, List<string> warnings)
        {
            errors.Clear();
            warnings.Clear();

            StartAttribute[] starts = (StartAttribute[])type.GetCustomAttributes(typeof(StartAttribute), true);
            if (starts.Length != 1)
            {
                errors.Add("There must be exactly one StartAttribute on the parser type");
                return false;
            }

            productions.AddRange(
                from m in type.GetMethods()
                from a in (RuleAttribute[])m.GetCustomAttributes(typeof(RuleAttribute), true)
                where m.Name.StartsWith("p_") || a.Name != null
                from p in Production.Parse(m, a.Name == null ? m.Name.Substring(2) : a.Name, a.Rule, kind, nonTerms, terms)
                select p);

            NonTerminal oldStart;
            if (!nonTerms.TryGetValue(starts[0].NonTerminal, out oldStart))
            {
                errors.Add("The selected start symbol was not found.");
                return false;
            }

            foreach (var item in from x in nonTerms where !x.Value.HasProductions select x.Value)
            {
                errors.Add("The non terminal '" + item + "' has no productions");
            }
            if (errors.Count > 0)
                return false;

            int i = 0; 
            OperatorAttribute[] operators = (OperatorAttribute[])type.GetCustomAttributes(typeof(OperatorAttribute), true);
            foreach (var item in operators)
            {
                item.Precidence = ++i;
                item.Type = kind[item.Name];
            }

            NonTerminal ntStart = new NonTerminal("$TART");
            nonTerms.Add("$TART", ntStart);
            Production pStart = new Production(null, ntStart, new ProductionNode[] { oldStart });
            productions.Add(pStart);

            CalculateFirst(ntStart, nonTerms, productions, kind);
            CalculateFollow(ntStart, nonTerms, productions, kind);

            LRItem start = new LRItem(0, pStart);
            LRItem end = new LRItem(1, pStart);
            LRItemSet startSet = new LRItemSet();
            startSet.Add(start);

            List<LRItem> kernels = new List<LRItem>();
            Queue<LRItemSet> setQueue = new Queue<LRItemSet>();
            setQueue.Enqueue(startSet);
            while (setQueue.Count > 0)
            {
                LRItemSet set = setQueue.Dequeue();
                kernels.Add(set.Kernel);
                states.Add(set);

                Closure(set);

                GetChildSets(setQueue, set, kernels);
            }

            Parser.Action[,] actions;
            int[,] gotos;
            GenerateTables(kind, operators, errors, warnings, end, out actions, out gotos);

            parser = new Parser(actions, gotos);

            return errors.Count == 0;
        }

        private void CalculateFirst(NonTerminal ntStart, Dictionary<string, NonTerminal> nonTerms, List<Production> productions, IEnum kind)
        {
            List<NonTerminal> done = new List<NonTerminal>();
            Stack<NonTerminal> history = new Stack<NonTerminal>();
            history.Push(ntStart);
            while (history.Count != 0)
            {
                NonTerminal nt = history.Peek();
                int c = history.Count;
                foreach (var item in nt.Productions)
                {
                    if (item.Nodes[0] is Terminal)
                        nt.first.Add(((Terminal)item.Nodes[0]).Type);
                    else
                    {
                        NonTerminal nt2 = (NonTerminal)item.Nodes[0];
                        if (!done.Contains(nt2))
                        {
                            if (!history.Contains(nt2))
                                history.Push(nt2);
                        }
                        else
                            nt.first.AddRange(nt2.first);
                    }
                    for (int i = 1; i < item.Nodes.Length; i++)
                    {
                        NonTerminal nt2 = item.Nodes[i] as NonTerminal;
                        if (nt2 != null && !done.Contains(nt2))
                        {
                            if (!history.Contains(nt2))
                                history.Push(nt2);
                        }
                    }
                }
                if (history.Count == c)
                    done.Add(history.Pop());
            }
        }

        private void CalculateFollow(NonTerminal ntStart, Dictionary<string, NonTerminal> nonTerms, List<Production> productions, IEnum kind)
        {
            ntStart.follow.Add(kind.MaximumValue + 1);
            List<Production> done = new List<Production>();
            Queue<NonTerminal> history = new Queue<NonTerminal>();
            history.Enqueue(ntStart);
            while (history.Count != 0)
            {
                NonTerminal nt = history.Dequeue();
                foreach (var item in nt.Productions)
                {
                    if (done.Contains(item)) continue;
                    ProductionNode next = item.Nodes.Length > 0 ? next = item.Nodes[0] : null;
                    for (int i = 0; i < item.Nodes.Length - 1; i++)
                    {
                        NonTerminal current = item.Nodes[i] as NonTerminal;
                        next = item.Nodes[i + 1];
                        if (current == null) continue;
                        if (next is NonTerminal)
                            current.follow.AddRange(((NonTerminal)next).first);
                        else
                            current.follow.Add(((Terminal)next).Type);
                        if (!history.Contains(current))
                            history.Enqueue(current);
                    }
                    if (next is NonTerminal)
                    {
                        NonTerminal current = (NonTerminal)next;
                        current.follow.AddRange(nt.follow);
                        if (!history.Contains(current))
                            history.Enqueue(current);
                    }
                    done.Add(item);
                }
            }
        }

        private void GenerateTables(IEnum kind, OperatorAttribute[] operators, List<string> errors, List<string> warnings, LRItem end, out Parser.Action[,] actions, out int[,] gotos)
        {
            actions = new Parser.Action[states.Count, kind.MaximumValue + 2];
            gotos = new int[states.Count, nonTerms.Count];
            List<NonTerminal> lNonTerms = new List<NonTerminal>(nonTerms.Values);
            List<Terminal> lTerms = new List<Terminal>(terms.Values);

            for (int i = 0; i < states.Count; i++)
                for (int j = 0; j < nonTerms.Count; j++)
                    gotos[i, j] = -1;

            for (int i = 0; i < states.Count; i++)
            {
                LRItemSet state = states[i];
                foreach (var item in state.Transitions)
                {
                    int newState = states.IndexOf(item.Value);
                    NonTerminal nt = item.Key as NonTerminal;
                    if (nt != null)
                    {
                        gotos[i, lNonTerms.IndexOf(nt)] = newState;
                        continue;
                    }
                    Terminal t = item.Key as Terminal;
                    if (t != null)
                    {
                        actions[i, t.Type] = new Parser.Shift(newState, item.Value);
                    }
                }
                foreach (var item in state)
                {
                    if (item.Dot != item.Production.Nodes.Length)
                        continue;

                    if (item.Equals(end))
                    {
                        actions[i, kind.MaximumValue + 1] = new Parser.Accept();
                        continue;
                    }

                    var reduce = new Parser.Reduce(lNonTerms, item.Production, productions.IndexOf(item.Production));
                    foreach (var t in GetTriggers(item, lTerms, kind))
                    {
                        actions[i, t] = ResolveConflict(t, operators, reduce, actions[i, t], errors, warnings);
                    }
                }
            }
        }

        private Parser.Action ResolveConflict(int next, OperatorAttribute[] operators, Parser.Reduce reduce, Parser.Action action, List<string> errors, List<string> warnings)
        {
            if (action == null)
                return reduce;
            if (action is Parser.Shift)
            {
                // only do operator stuff for productions like:
                //  E : A OP B
                if (reduce.production.Nodes.Length == 3
                    && reduce.production.Nodes[0] is NonTerminal
                    && reduce.production.Nodes[1] is Terminal
                    && reduce.production.Nodes[2] is NonTerminal)
                {
                    Parser.Action result = DoOperatorResolution(next, operators, reduce, action);
                    if (result != null)
                        return result;
                }

                warnings.Add(action.Conflict(reduce));
                return action;
            }
            if (action.ToString() == reduce.ToString())
            {
                errors.Add(string.Format("Duplicate: {0} is declared twice", reduce.production));
                return reduce;
            }
            errors.Add(action.Conflict(reduce));
            return reduce;
        }

        private static Parser.Action DoOperatorResolution(int next, OperatorAttribute[] operators, Parser.Reduce reduce, Parser.Action action)
        {
            int leftTok = ((Terminal)reduce.production.Nodes[1]).Type;
            OperatorAttribute leftOp = null;
            OperatorAttribute rightOp = null;

            foreach (var item in operators)
            {
                if (item.Type == leftTok)
                    leftOp = item;
                if (item.Type == next)
                    rightOp = item;
                if (leftOp != null && rightOp != null)
                    break;
            }

            if (leftOp != null && rightOp != null)
            {
                if (leftOp.Precidence > rightOp.Precidence)
                    return reduce;
                if (leftOp.Precidence < rightOp.Precidence)
                    return action;
                if (leftOp == rightOp)
                {
                    if (leftOp != null)
                    {
                        switch (leftOp.Associativity)
                        {
                            case OperatorAssociativity.Left:
                                return reduce;
                            case OperatorAssociativity.Right:
                                return action;
                        }
                    }
                }
            }

            return null;
        }

        private IEnumerable<int> GetTriggers(LRItem item, List<Terminal> lTerms, IEnum kind)
        {
            return item.Production.Name.follow;
        }

        private void GetChildSets(Queue<LRItemSet> setQueue, LRItemSet parentSet, List<LRItem> kernels)
        {
            List<LRItem> list = new List<LRItem>();
            list.AddRange(from i in parentSet
                          where i.Dot < i.Production.Nodes.Length
                          select new LRItem(i.Dot + 1, i.Production));

            while (list.Count != 0)
            {
                LRItemSet childSet = new LRItemSet();
                LRItem child = list[0];

                childSet.AddRange(from i in list
                                  where i.Previous == child.Previous
                                  select i);
                foreach (var item in childSet)
                    list.Remove(item);

                if (!kernels.Contains(childSet.Kernel))
                    setQueue.Enqueue(childSet);
                else
                {
                    childSet = (from s in states 
                               where s.Kernel.Equals(childSet.Kernel)
                               select s).First();
                }
                parentSet.AddTransition(child.Previous, childSet);
            }
        }

        void Closure(LRItemSet set)
        {
            for (int ix = 0; ix < set.Count; ix++)
            {
                ProductionNode node = set[ix].Current;
                NonTerminal nt = node as NonTerminal;
                if (nt != null)
                {
                    set.AddRange(from p in nt.Productions
                                 select new LRItem(0, p));
                }
            }
        }
    }
}
